package com.example.temp;

import java.util.Arrays;

public class Test4oooo {

    public static void main(String[] args) {

    }


    public class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            data = x;
        }
    }


    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
     */
    public class Solution {
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            //数组长度为0的时候要处理
            if (pre.length == 0) return null;

            //因为前序遍历第一个元素就是root
            int rootVal = pre[0];

            //数组长度仅为1的时候就要处理
            if (pre.length == 1) return new TreeNode(rootVal);
            //我们先找到root所在的位置，确定好前序和中序中左子树和右子树序列的范围
            //因为前序遍历第一个元素就是root 所以：找到值相等的就是root在中序遍历的位置
            int rootindex = 0;
            for (int i = 0; i < in.length; i++) {
                if (rootVal==in[i]){
                    rootindex =i;
                    break;
                }
            }
            TreeNode root = new TreeNode(rootVal);

            //递归，假设root的左右子树都已经构建完毕，那么只要将左右子树安到root左右即可
            //这里注意Arrays.copyOfRange(int[],start,end)是[)的区间
            //Arrays.copyOfRange(pre,1,rootindex+1)因为rootindex是中序遍历root节点，所以对于前序遍历左子树节点正好
            //是rootindex个数，所以截取前序遍历数组应该这么截[)的区间

            root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootindex+1),
                    Arrays.copyOfRange(in,0,rootindex));
            root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootindex+1,pre.length)
                    , Arrays.copyOfRange(in,rootindex,in.length));

            return root;
        }

        public TreeNode reConstructBinaryTreeTest(int[] pre, int[] in){
            if(pre.length==0)return null;
            TreeNode root = null;
            for (int i = 0; i < in.length; i++) {
                if (pre[0]==in[i]){
                    root = new TreeNode(pre[0]);
                    root.left = reConstructBinaryTreeTest(Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(in,0,i));
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length), Arrays.copyOfRange(in,i+1,in.length));
                }

            }
            return root;
        }
    }


}
